//
//  main.cpp
//  PrimeNumberFilterMethod
//
//  Created by DeLong Yang on 2017/8/2.
//  Copyright © 2017年 YiXue. All rights reserved.
/*
    blog：https://baike.baidu.com/item/%E7%AD%9B%E6%B3%95%E6%B1%82%E7%B4%A0%E6%95%B0/8670409?fr=aladdin&fromid=15458451&fromtitle=%E7%B4%A0%E6%95%B0%E7%AD%9B%E6%B3%95
 
    this program is to show primeNumberFilter
 
 */

#include <iostream>
#include <cmath>

using namespace std;

// get the 1-1000 prime number
// 使用空间 来减少 时间计算的
void simple()
{
    int pre[1002];
    int i,k;
    //
    for (i = 1; i<1000; i++)
    {
        pre[i] = i;   //  fill number
    }
    
    //
    pre[1] = 0;  // 2 是 最小的素数
    
    // 问题的关键是 i*k 和 pre[i*k] 的值是相等的 如果改变顺序是否呢？
    for (i=1;i<1000;i++)
    {
        if (pre[i] != 0) { //
            //
            for (k=2; i*k<1000; k++) {
                pre[i*k] = 0;
            }
        }
    }
    
    //
    for (i = 1; i<1000; i++)
    {
        if (pre[i] != 0) {
            printf("%d \n",pre[i]);
        }
    }
}

// 我们打乱 顺序 try again 素树筛 是在一个连续的范围内的。
void simpleExpri()
{
    int pre[1002] = {2,5,8,9,12,15,3};
    int i,k;
    // 问题的关键是 i*k 和 pre[i*k] 的值是相等的 如果改变顺序那就不行了
    //
    for (i=0;i<7;i++)
    {
        if (pre[i] != 0) { //
            //
            for (k=2; i*k<1000; k++) {
                pre[i*k] = 0;
            }
        }
    }
    
    //
    for (i = 1; i<1000; i++)
    {
        if (pre[i] != 0) {
            printf("%d \n",pre[i]);
        }
    }
}

// official demo   but I think this is not very good
//  这是一个连续的 数字的串
//  为了减少 空间占用。增加了 时间复杂度
//  I did alittle change to che programe
/*
 说明：解决这个问题的诀窍是如何安排删除的次序，使得每一个非质数都只被删除一次。 中学时学过一个因式分解定理，他说任何一个非质（合）数都可以分解成质数的连乘积。例如，16=2^4，18=2 * 3^2，691488=2^5 * 3^2 * 7^4等。如果把因式分解中最小质数写在最左边，有16=4^2，18=2*9,691488=2^5 * 21609,；换句话说，把合数N写成N=p^k * q，此时q当然是大于p的，因为p是因式分解中最小的质数。由于因式分解的唯一性，任何一个合数N，写成N=p^k * q;的方式也是唯一的。 由于q>=p的关系，因此在删除非质数时，如果已知p是质数，可以先删除p^2,p^3,p^4,... ，再删除pq,p^2*q,p^3*q,...,（q是比p大而没有被删除的数），一直到pq>N为止。
 因为每个非质数都只被删除一次，可想而知，这个程序的速度一定相当快。依据Gries与Misra的文章，线性的时间，也就是与N成正比的时间就足够了（此时要找出2N的质数）。 （摘自《C语言名题精选百则（技巧篇）》，冼镜光 编著，机械工业出版社，2005年7月第一版第一次印刷）。代码如下：
 */
void FilterPrime()
{
    int N;
    cin>>N;
    int *location = new int[N+1];
    for (int i=0; i!= N+1; ++i) {
        location[i] = i;
    }
    location[1] = 0;  //
    int p,q,end;
    end = sqrt(double(N))+1;//  至于为什么 end 的值 p^n*q <=N  数组中最大值是N p>=2,q>=p; N>=2; 都是整数值
    
    
    //
    printf("end index is: %d \n",end);
    for (p=2;p<=end;++p){
        //
        if (location[p]) {
            for (q=p; p*q <=N;++q){
                for (int k=p*q;k<=N;k*=p){
                    location[k] = 0;
                }
            }
        }
    }
    
    for (int i=0; i<N+1;i++){
        if (location[i]) {
            cout<<location[i]<<" ";
        }
    }
    // 下面这些 是 官方 无用的代码
//    int m=0;
//    for (int i=0;i!=N+1;i++){
//        if (location[i] != 0){
//            cout<<location[i]<<" ";
//            ++m;
//        }
//        
//        if (m%10 == 0) {
//            cout<<end;
//        }
//        
//        cout<<end<<m<<end;
//
//    }
    
    
}


int main(int argc, const char * argv[]) {
    // insert code here...
//    std::cout << "Hello, World!\n";
//    simple();
    
    FilterPrime();
    
    return 0;
}
